#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
#endif

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        dfs(candidates, target, 0);
        return res;
    }

    vector<vector<int>> res;
    vector<int> tmp;

    void dfs(vector<int> candidates, int target, int index) {
        if (target < 0) return;
        if (target == 0) {
            res.push_back(tmp);
            return;
        }
        if (index == candidates.size()) return; //注意：这段要放在最后！（不加这行 由于index，会产生数组越界）
        for (int i = 0; candidates[index] * i <= target; i++) { //注意：这里要加等号。（等号时，之后的元素都是0个）
            for (int j = 0; j < i; j++) tmp.push_back(candidates[index]);
            dfs(candidates, target - i * candidates[index], index + 1);
            for (int j = 0; j < i; j++) tmp.pop_back();
        }
    }
};

#ifdef LOCAL
int main() {
    freopen("../LeetCode/in.txt", "r", stdin);
    vector<int> a = {2, 3, 6, 7};
    int target = 7;
    Solution solution;
    vector<vector<int>> res;
    res = solution.combinationSum(a, target);
}
#endif